МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” / Кафедра ЕОМ КУРСОВА РОБОТА ( Частина 2 ) НА ТЕМУ: "Представлення в пам’яті комп’ютера статичних даних" Вибір варіанту: Вибір АТД: 2 = [8 +12 + 83 ] % 3 + 1 Вибір номера завдання: 2 = [8 + 83 ] % 10 + 1    Зміст 2. Завдання 2: Динамічні структури даних………………………………………………………………3 2.1. Теоретична частина……………………………………………………………………...…………………3 2.2. Частина 1. Побудова АТД………………………………………………………………...……………...6 2.2.1. Постановка задачі………………………………………………………………....…………………6 2.2.2. Динаміка вмісту………………………………………………………………...……………………..6 2.2.3. Результати виконання програми …………………………………………………………...8 2.3. Частина 2. Застосування АТД………………………………………………………………...………9 2.3.1. Постановка задачі………………………………………………………………...…………………9 2.3.2. Алгоритм розв’язання задачі……………………………………………………………….....9 2.3.3. Результати виконання програми……………………………………………………………10 Висновки………………………………………………………………...………………………………………………….11 Список літератури………………………………………………………………...…………………………………..12 Додатки………………………………………………………………...……………………………………………………13  2. Завдання 2: Динамічні структури даних 2.1 Теоретична частина Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO. Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу. Приклад : В послідовності 8 2 6 3 1 4 9 кожна парна цифра визначає операцію push (додавання цієї цифри в чергу), а кожна непарна цифра визначає операцію pop (вилученя з черги одного елемента). Введемо такі позначення: P – покажчик початку черги, К – покажчик кінця черги Наведемо динаміку вмісту черги під час обробки заданої послідовності:  K P  0)       - порожня черга      P K   P K   P K  1) 8       2) 8 2      3) 8 2 6        P K   P K   P K  4)  2 6     5)   6     6)   6 4       P K      7)    4            Оскільки черга - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас queue, для використання якого потрібно включити заголовочний файл: # include <queue> Набір стандартних операцій роботи з чергою показаний у таблиці: Операція Дія  push(іtem) Поміщає новий елемент у кінець черги  pop() Вилучає елемент з черги, але не повертає його значення  front() Повертає значення елемента з початку черги, але не вилучає його  empty() Повертає true, якщо черга порожня, і false у противному випадку  sіze() Повертає кількість елементів у черзі   Розглянемо статичну реалізацію черги на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу queue, аналогічний класу queue зі стандартної бібліотеки шаблонів STL. // ФАЙЛ: queue1.h (частина простору імен main_savitch_8B) #ifndef MAIN_SAVITCH_QUEUE1_H #define MAIN_SAVITCH_QUEUE1_H #include <cstdlib> // Provides size_t namespace main_savitch_8B { template <class Item> class queue { public: // ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ typedef std::size_t size_type; typedef Item value_type; static const size_type CAPACITY = 30; // КОНСТРУКТОР queue( ); // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void pop( ); void push(const Item& entry); // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty( ) const { return (count == 0); } Item front( ) ...